	#include <iostream>
	#include <map>
	#include <string>
	using namespace std;

	int MAX = 10000;

	bool primes[10000];

	int usefulPrimes[10000];

	map<int, int> mapp;

	int TABLE_SIZE = 1061;

	int table[1061][1061];

	int counter = 2;
		
	void createPrimes() {
	   int i, j;

	   for(i = 0; i < MAX; i++) {
	      primes[i] = false;
	   }

	   primes[2] = true;
	   primes[3] = true;
			   

	   for(i = 5; i < MAX; i+=2) {
	       for(j = 3; j*j <=i ; j+=2)
	           if(i % j == 0) break;
		   if(i % j != 0 )  {
		   	   primes[i] = true;
		   	   counter++;
		   }
	 	}
		   
	}



	void process() {
		int cases;
		cin >> cases;
			
		for (int k = 0; k < cases; k++) {
				
			int a;
			int b;
			cin >> a;
			cin >> b;

			if (a > b) {
				int aux = a;
				a = b;
				b = aux;
			}

			int aIndex = mapp[a];
							
			int bIndex = mapp[b];
				
			int value = table[aIndex][bIndex];
				
			if (value == 99999999) {
				cout << "Impossible\n";
			} else {
				cout << value << "\n";
			}
				
		}
			
	}


	int main() {

		createPrimes();

		int index = 0;
			
			
		for (int k = 0; k < MAX; k++) {
			if (primes[k]) {
				if (k > 999) {
					usefulPrimes[index] = k;
					mapp[k] = index;
					index++;
				}
					
				if (k > 10000) break;
			}
		}

		for (int i = 0; i < index; i++) {
			for (int j = 0; j < index; j++) {
				table[i][j] = 99999999; 
			}
		}


		for (int k = 0; k < index; k++) {
			int number[4];
			int usefulPrime = usefulPrimes[k];
					
			number[0] = usefulPrime / 1000;  
			number[1] = (usefulPrime % 1000) / 100;
			number[2] = (usefulPrime % 100) / 10;
			number[3] = (usefulPrime % 10);

			int dummyPrime;
				
				
			for (int j = 1; j < 10; j++) {
				number[0] = j;
					
				if (primes[number[0] * 1000 + number[1] * 100 + number[2] * 10 + number[3]]) {
					dummyPrime = number[0] * 1000 + number[1] * 100 + number[2] * 10 + number[3];
						
					table[k][mapp[dummyPrime]] = 1;
					table[mapp[dummyPrime]][k] = 1;
						
				}

					
			}
				
			number[0] = usefulPrime / 1000;
				
			for (int i = 1; i < 4; i++) {

				int usefulPrime = usefulPrimes[k];
					
				number[1] = (usefulPrime % 1000) / 100;
				number[2] = (usefulPrime % 100) / 10;
				number[3] = (usefulPrime % 10);
					
				for (int j = 0; j < 10; j++) {
					number[i] = j;
						
					if (primes[number[0] * 1000 + number[1] * 100 + number[2] * 10 + number[3]]) {
						dummyPrime = number[0] * 1000 + number[1] * 100 + number[2] * 10 + number[3];
							
						table[k][mapp[dummyPrime]] = 1;
						table[mapp[dummyPrime]][k] = 1;
							
					}
						
				}
					
			}

		}


		for (int i = 0; i < index; i++) {
			table[i][i] = 0;
		}


		int value;
			
		int valueIK;
			
		for (int k = 0; k < TABLE_SIZE; k++) {
				
			for (int i = 0; i < TABLE_SIZE; i++) {
					
				valueIK = table[i][k]; 
					
				if (valueIK >= 5) continue;
					
				for (int j = 0  ; j < TABLE_SIZE; j++) {

					value = valueIK + table[k][j];
						
					if (table[i][j] > value) {
						table[i][j] = value;
					}
				}
			}
		}

		process();
	}	
